//Given the head of a linked list, return the list after sorting it in ascending
// order. 
//
// Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.
//e. constant space)? 
//
// 
// Example 1: 
//
// 
//Input: head = [4,2,1,3]
//Output: [1,2,3,4]
// 
//
// Example 2: 
//
// 
//Input: head = [-1,5,3,4,0]
//Output: [-1,0,3,4,5]
// 
//
// Example 3: 
//
// 
//Input: head = []
//Output: []
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the list is in the range [0, 5 * 104]. 
// -105 <= Node.val <= 105 
// 
// Related Topics 排序 链表 
// 👍 1181 👎 0

package leetcode.editor.cn;

class P148SortList {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(4);
        ListNode node2 = new ListNode(19);
        ListNode node3 = new ListNode(14);
        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(-3);
        ListNode node6 = new ListNode(1);
        ListNode node7 = new ListNode(8);
        ListNode node8 = new ListNode(5);
        ListNode node9 = new ListNode(11);
        ListNode node10 = new ListNode(15);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;
        node9.next = node10;
        Solution solution = new P148SortList().new Solution();
        ListNode listNode = solution.sortList(node1);
        System.out.println(listNode);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode sortList(ListNode head) {
            return sortList(head, null);
        }

        private ListNode sortList(ListNode head, ListNode tail) {
            if (head == null) {
                return null;
            }
            if (head == tail) {
                return head;
            }
            ListNode slowNode = head;
            ListNode fastNode = head;
            while (fastNode != null && fastNode.next != null && slowNode.next != tail) {
                slowNode = slowNode.next;
                fastNode = fastNode.next.next;
            }
            ListNode mid = slowNode.next;
            slowNode.next = null;
            ListNode l1 = sortList(head, slowNode);
            ListNode l2 = sortList(mid, tail);
            return mergeListNode(l1, l2);

        }

        private ListNode mergeListNode(ListNode l1, ListNode l2) {
            ListNode l1Node = l1;
            ListNode l2Node = l2;
            ListNode dumpyNode = new ListNode(Integer.MIN_VALUE);
            ListNode saveNode = dumpyNode;
            while (l1Node != null || l2Node != null) {
                while (l1Node != null && l2Node != null && l1Node.val <= l2Node.val) {
                    saveNode.next = l1Node;
                    l1Node = l1Node.next;
                    saveNode = saveNode.next;
                }
                while (l1Node != null && l2Node != null && l1Node.val >= l2Node.val) {
                    saveNode.next = l2Node;
                    l2Node = l2Node.next;
                    saveNode = saveNode.next;
                }
                while (l2Node == null && l1Node != null) {
                    saveNode.next = l1Node;
                    l1Node = l1Node.next;
                    saveNode = saveNode.next;
                }
                while (l1Node == null && l2Node != null) {
                    saveNode.next = l2Node;
                    l2Node = l2Node.next;
                    saveNode = saveNode.next;
                }
            }

            return dumpyNode.next;
        }

        //1.自底向上
        public ListNode sortList2(ListNode head) {
            if (head == null) {
                return head;
            }
            int length = 0;
            ListNode node = head;
            while (node != null) {
                length++;
                node = node.next;
            }
            ListNode dummyHead = new ListNode(0);
            for (int subLength = 1; subLength < length; subLength <<= 1) {
                ListNode prev = dummyHead, curr = dummyHead.next;
                while (curr != null) {
                    ListNode head1 = curr;
                    for (int i = 1; i < subLength && curr.next != null; i++) {
                        curr = curr.next;
                    }
                    ListNode head2 = curr.next;
                    curr.next = null;
                    curr = head2;
                    for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
                        curr = curr.next;
                    }
                    ListNode next = null;
                    if (curr != null) {
                        next = curr.next;
                        curr.next = null;
                    }
                    ListNode merged = merge(head1, head2);
                    prev.next = merged;
                    while (prev.next != null) {
                        prev = prev.next;
                    }
                    curr = next;
                }
            }
            return dummyHead.next;
        }

        public ListNode merge(ListNode head1, ListNode head2) {
            ListNode dummyHead = new ListNode(0);
            ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
            while (temp1 != null && temp2 != null) {
                if (temp1.val <= temp2.val) {
                    temp.next = temp1;
                    temp1 = temp1.next;
                } else {
                    temp.next = temp2;
                    temp2 = temp2.next;
                }
                temp = temp.next;
            }
            if (temp1 != null) {
                temp.next = temp1;
            } else if (temp2 != null) {
                temp.next = temp2;
            }
            return dummyHead.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}